Message authentication is a technique of assuring the authenticity of a message by attaching, to the message, a tag that can be computed only by those who know a secret key. For example, the use of message authentication enables the detection of whether or not communication between two parties sharing a secret key has been tampered with by a third party. A specific example is given below. Let K be a secret key shared by the sender and receiver of a message. For a message M, the sender sends a tag T=MAC (K, M) computed by assigning M and K to a message authentication code (MAC) function F, to the receiver. Having received a message M′ and a tag T′, the receiver computes a tag T″ from the shared key K and M′, and checks whether or not the received tag T′ and the computed tag T″ match. The receiver can thus verify whether or not the message M′ is from the stated sender.
One of the message authentication schemes is a CBC-MAC scheme using a block cipher. The term “message authentication scheme” is hereafter referred to as “MAC scheme” or simply “MAC”. CBC-MAC is a MAC that uses, as its component, an encryption function E(K, *) of an n-bit block cipher with K as a key. CBC-MAC operates as follows. Let |M| be the length of a message M. In the case where |M| is a multiple of n, M is first divided into blocks M[1], M[2], . . . , M[m] (|M[1]|= . . . =|M[m]|=n), where m is the number of blocks. Then, Y[m] is output as a tag through the following computation.Y[1]=E(K,M[1]),Y[2]=E(K,M[2]+Y[1]), . . . Y[m]=E(K,M[m]+Y[m−1]).
Here, 0^n is an n-bit all-zero sequence, and “+” denotes a bitwise exclusive-or (XOR).
In the case where the length of the message is not a multiple of n, the message is first padded to make its length a multiple of n, before applying CBC-MAC. Simple CBC-MAC is easy to be forged when the message length is variable. For example, in the case where Y[1]=E(K, M[1]) is obtained as a tag for M=M[1], a tag generated for M′=(M[1], M[1]+Y[1]) is invariably Y[1].
OMAC described in Non Patent Literature (NPL) 1 is an improvement of CBC-MAC that removes the above-mentioned security drawback. OMAC is equivalent to CMAC recommended by NIST, and so is hereafter referred to as “CMAC”. In CMAC, the result of encrypting 0^n is held beforehand, and an intermediate variable of CBC-MAC is changed using the held value only in the encryption of the last block. In detail, CMAC operates as follows. When a message M is given, M is divided into blocks M[1], M[2], . . . , M[m] (|M[1]|= . . . =|M[m−1]|=n, 1≦|M[m]|≦n), and Y[m] is output as a tag using the following Formula 1.L=E(K,0^n),Y[1]=E(K,M[1]),Y[2]=E(K,M[2]+Y[1]), . . . ,Y[m−1]=E(K,M[m−1]+Y[m−2]),Y[m]=E(K,M[m]+Y[m−1]+2L) if |M[m]|=n, Y[m]=E(K,(M[m]∥10*)+Y[m−1]+4L) if |M[m]|≦n  (Formula 1).
Here, (M[m]∥10*) is an n-bit sequence obtained by padding M[m] with 10 . . . 0. 2L is multiplication by a generator of a finite field (Galois field) GF(2^n) where L is an element of the field, and corresponds to multiplication by 2 in the finite field. 4L denotes 2(2L), and corresponds to multiplication by 2 twice. FIG. 5 is an explanatory diagram illustrating tag output in CMAC. In FIG. 5, EK denotes an encryption function of an n-bit block cipher with K as a key. “∥” denotes a concatenation operator for a bit string.
CMAC has the feature that, by computing L in Formula 1 beforehand, any message M can be processed with ceiling(|M|/n) block cipher calls. One block typically needs at least one block cipher call, according to security definition. Hence, this number of block cipher calls is a minimum number, except for precomputation.
TMAC described in NPL 2 and XCBC described in NPL 3 are approximately the same process as CMAC mentioned above but, instead of using 2L or 4L in the last block, use a value generated from a key other than the block cipher key K. TMAC and XCBC therefore do not need precomputation of E(K, 0^n), but have a drawback in that the MAC key is longer than that of CMAC.
GCBC described in NPL 5 is an improvement for omitting the precomputation in CMAC while using only the block cipher key K as the MAC key. In GCBC and particularly GCBC1 described in NPL 5, Y[m] is output as a tag using the following Formula 2.
When |M|>n,Y[1]=E(K,M[1]),Y[2]=E(K,M[2]+Y[1]), . . . ,Y[m−1]=E(K,M[m−1]+Y[m−2]),Y[m]=E(K,M[m]+(Y[m−1]<<<1)) if |M[m]|=n, Y[m]=E(K,(M[m]∥10*)+(Y[m−1]<<<2)) if |M[m]|≦n  (Formula 2).
Here, (Y[m−1]<<<i) is the value obtained by shifting (logical shift) Y[m−1] left by i bits, where the right bits are filled in with zeros. When |M|=n, Y[2] is output as a tag in GCBC1 using the following formula.Y[1]=E(K,M[1]),Y[2]=E(K,(10^n−1)+(Y[1]<<<2)).
When |M|<n, Y[2] is output as a tag in GCBC1 using the following formula.Y[1]=E(K,(M[1]∥10*)),Y[2]=E(K,(0^n)+(Y[1]<<<2)).
In GCBC1, when |M|>n, the process is completed with ceiling(|M|/n) block cipher calls with no need for precomputation. When |M|≦n, on the other hand, two block cipher calls are needed. FIG. 6A is an explanatory diagram illustrating tag output in GCBC in the case where the number m of blocks of the message is 2 or more. In FIG. 6A, “<<i” denotes an i-bit logical left shift. FIG. 6B is an explanatory diagram illustrating tag output in GCBC in the case where the number m of blocks of the message is 1.
Each of the schemes described above makes one block cipher call per message block, and so is incapable of processing blocks in parallel.
PMAC described in NPL 4 is a MAC scheme capable of processing blocks in parallel. When a message M is given, M is divided into blocks M[1], M[2], . . . , M[m] (|M[1]|= . . . =|M[m−1]|=n, 1≦|M[m]|≦n), as in CMAC. Then, T is output as a tag using the following Formula 3. In the formula, 3L denotes 2L+L.L=E(K,0^n),S[i]=E(K,(2^i)L+M[i]) for i=1, . . . ,m−1V=S[1]+S[2]+ . . . +S[m−1]T=E(K,V+M[m]+2^(m−1)L3L) if |M[m]|=n, T=E(K,V+(M[m]∥10*)+2^(m−1)L(3^2)L) if |M[m]|≠n  (Formula 3).
PMAC differs from CBC-MAC, CMAC, and GCBC in that it is parallelizable except for the last one block. Moreover, PMAC can complete the entire process with ceiling(|M|/n) block cipher calls if L is precomputed, as with CMAC. FIG. 7 is an explanatory diagram illustrating tag output in PMAC. In FIG. 7, 2m-1L, i.e. 2iL, denotes multiplication by 2i in a finite field GF(2^n) of L, and 32L, i.e. 3iL, denotes multiplication by 3i in the finite field GF(2^n) of L.
Other MAC schemes that are parallelizable include XOR MAC described in NPL 6. In XOR MAC, however, input to a block cipher includes information other than an input message, such as block indices. Accordingly, XOR MAC typically needs ceiling(|M|/m) block cipher calls (for some m<n) for a message M, which is larger than the number of block cipher calls in PMAC.
The schemes described in NPL 1, NPL 4, and NPL 5 are MAC schemes capable of computing output from only a secret key and a message. Such schemes are called deterministic MACs.
PAT described in NPL 7 is known as another MAC that is parallelizable. However, PAT needs random number generation for MAC generation, and belongs to randomized MACs. In randomized MACs, a random number used needs to be included in part of output, which causes an increase in output size as compared with deterministic MACs.
There is a message authentication device that combines a block cipher and part of its components to attain higher speed than existing block cipher authentication schemes, exhibit theoretical security, and improve efficiency in the preprocessing and the amount of memory used (for example, see Patent literature (PTL) 1). There is also a device that reads a plurality of blocks of an input message in parallel and reduces each block to decrease the number of data inputs to the subsequent encrypter, thus improving the authenticator generation speed (for example, see PTL 2).